#include <iostream>
using namespace std;

int findKey(int* arr, int left, int right)
{
	int prev = left, cur = left + 1;

	while (cur <= right)
	{
		if(arr[cur] < arr[left] && ++prev != cur)
		{
			swap(arr[cur], arr[prev]);
		}
		cur++;
	}
	swap(arr[prev], arr[left]);
	
	return prev;
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;

	int keyi = findKey(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

int main()
{
	int arr[] = { 3,5,4,6,2,0,7,9,1,8 };
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;

	QuickSort(arr, 0, 9);

	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;

	return 0;
}